home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / programming / source / graphicgems4.lha / GemsIV / thin_image.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-02-06  |  4.8 KB  |  162 lines
  1. /*
  2.  * C code from the article
  3.  * "Efficient Binary Image Thinning using Neighborhood Maps"
  4.  * by Joseph M. Cychosz, 3ksnn64@ecn.purdue.edu
  5.  * in "Graphics Gems IV", Academic Press, 1994
  6.  */
  7.  
  8. #include <stdio.h>
  9.  
  10. typedef unsigned char    Pixel;        /* Pixel data type        */
  11.  
  12. typedef struct    {            /* Image control structure    */
  13.     short    Hres;            /*   Horizontal resolution (x)    */
  14.     short    Vres;            /*   Vertical    resolution (y)    */
  15.     int    Size;            /*   Image size (bytes)        */
  16.     Pixel    *i;            /*   Image array        */
  17.     Pixel    *p[1];            /*   Scanline pointer array    */
  18.                     /*   Pixel (x,y) is given by    */
  19.                     /*   image->p[y][x]        */
  20. }    Image;
  21.  
  22.  
  23. /* ---- ThinImage - Thin binary image. -------------------------------- */
  24. /*                                    */
  25. /*    Description:                            */
  26. /*        Thins the supplied binary image using Rosenfeld's parallel    */
  27. /*        thinning algorithm.                        */
  28. /*                                    */
  29. /*    On Entry:                            */
  30. /*        image = Image to thin.                    */
  31. /*                                    */
  32. /* -------------------------------------------------------------------- */
  33.  
  34.  
  35.                 /* Direction masks:            */
  36.                 /*   N       S     W     E        */
  37. static    int    masks[]        = { 0200, 0002, 0040, 0010 };
  38.  
  39. /*    True if pixel neighbor map indicates the pixel is 8-simple and    */
  40. /*    not an end point and thus can be deleted.  The neighborhood    */
  41. /*    map is defined as an integer of bits abcdefghi with a non-zero    */
  42. /*    bit representing a non-zero pixel.  The bit assignment for the    */
  43. /*    neighborhood is:                        */
  44. /*                                    */
  45. /*                a b c                    */
  46. /*                d e f                    */
  47. /*                g h i                    */
  48.  
  49. static    unsigned char    delete[512] = {
  50.         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  51.         0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1,
  52.         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  53.         0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1,
  54.         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  55.         0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1,
  56.         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  57.         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1,
  58.         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  59.         0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1,
  60.         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  61.         1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  62.         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  63.         1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1,
  64.         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  65.         1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  66.         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  67.         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  68.         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  69.         1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1,
  70.         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  71.         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  72.         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  73.         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1,
  74.         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  75.         1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1,
  76.         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  77.         1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  78.         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  79.         1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1,
  80.         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  81.         1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
  82.  
  83. void    ThinImage    (image)
  84.  
  85.     Image        *image;        /* Image control structure    */
  86.  
  87. {
  88.     int        xsize, ysize;    /* Image resolution        */
  89.     int        x, y;        /* Pixel location        */
  90.     int        i;        /* Pass index            */
  91.     int        pc    = 0;    /* Pass count            */
  92.     int        count    = 1;    /* Deleted pixel count        */
  93.     int        p, q;        /* Neighborhood maps of adjacent*/
  94.                     /* cells            */
  95.     Pixel        *qb;        /* Neighborhood maps of previous*/
  96.                     /* scanline            */
  97.     int        m;        /* Deletion direction mask    */
  98.  
  99.     xsize = image->Hres;
  100.     ysize = image->Vres;
  101.     qb    = (Pixel *) malloc (xsize*sizeof(Pixel));
  102.     qb[xsize-1] = 0;        /* Used for lower-right pixel    */
  103.  
  104.     while ( count ) {        /* Scan image while deletions    */
  105.         pc++;
  106.         count = 0;
  107.  
  108.         for ( i = 0 ; i < 4 ; i++ ) {
  109.  
  110.         m = masks[i];
  111.  
  112.         /* Build initial previous scan buffer.            */
  113.  
  114.         p = image->p[0][0] != 0;
  115.         for ( x = 0 ; x < xsize-1 ; x++ )
  116.             qb[x] = p = ((p<<1)&0006) | (image->p[0][x+1] != 0);
  117.  
  118.         /* Scan image for pixel deletion candidates.        */
  119.  
  120.         for ( y = 0 ; y < ysize-1 ; y++ ) {
  121.  
  122.             q = qb[0];
  123.             p = ((q<<3)&0110) | (image->p[y+1][0] != 0);
  124.  
  125.             for ( x = 0 ; x < xsize-1 ; x++ ) {
  126.             q = qb[x];
  127.             p = ((p<<1)&0666) | ((q<<3)&0110) |
  128.                 (image->p[y+1][x+1] != 0);
  129.             qb[x] = p;
  130.             if  ( ((p&m) == 0) && delete[p] ) {
  131.                 count++;
  132.                 image->p[y][x] = 0;
  133.             }
  134.             }
  135.  
  136.             /* Process right edge pixel.            */
  137.  
  138.             p = (p<<1)&0666;
  139.             if    ( (p&m) == 0 && delete[p] ) {
  140.             count++;
  141.             image->p[y][xsize-1] = 0;
  142.             }
  143.         }
  144.  
  145.         /* Process bottom scan line.                */
  146.  
  147.         for ( x = 0 ; x < xsize ; x++ ) {
  148.             q = qb[x];
  149.             p = ((p<<1)&0666) | ((q<<3)&0110);
  150.             if    ( (p&m) == 0 && delete[p] ) {
  151.             count++;
  152.             image->p[ysize-1][x] = 0;
  153.             }
  154.         }
  155.         }
  156.  
  157.         printf ("ThinImage: pass %d, %d pixels deleted\n", pc, count);
  158.     }
  159.  
  160.     free (qb);
  161. }
  162.